package util

import java.math.BigDecimal
import java.util

import scala.util.Try

/**
  * Created by liuwei on 2018/2/6.
  */
object HeapSort {

  def main(args: Array[String]): Unit = {
    val list = scala.collection.mutable.MutableList.empty[Int]
    val a = System.currentTimeMillis()
    for(i <- 0 until 100000){
      list += i
    }
    val b = System.currentTimeMillis()
    println(b-a)
    val array = scala.collection.mutable.ArrayBuffer.empty[Int]
    val c = System.currentTimeMillis()
    for(i <- 0 until 100000){
      array += i
    }
    val d = System.currentTimeMillis()
    println(d-c)
    val vector = new util.Vector[Int]()
    val e = System.currentTimeMillis()
    for(i <- 0 until 100000){
      vector.add(i)
    }
    val f= System.currentTimeMillis()
    println(f-e)
    val arrayList = new util.ArrayList[Int]()
    val g = System.currentTimeMillis()
    for(i <- 0 until 100000){
      arrayList.add(i)
    }
    val h= System.currentTimeMillis()
    println(h-g)




//    val arr= Array(9,5,6,7,5,2,9)
//    heapSort(arr)
//    println(arr.foreach(println))

  }

  def heapSort(arr:Array[Int]):Unit={
    makeHeap(arr)
    var i= arr.length-1
    while(i >= 0){
      swap(arr,0,i)
      adjustDown(arr,0,i)
      i -= 1
    }

  }

  def makeHeap(arr:Array[Int]):Unit ={
    var i= arr.length/2-1
    while(i >=0){
      adjustDown(arr,i,arr.length)
      i -=1
    }
  }


  def adjustDown(arr:Array[Int],i:Int,n:Int):Unit={
    var i2 = i
    val temp = arr(i)
    //先取出当前元素i
    var k = i2 * 2 + 1
    while (k < n) { //从i结点的左子结点开始，也就是2i+1处开始
      if (k + 1 < n && arr(k) < arr(k + 1)) { //如果左子结点小于右子结点，k指向右子结点
        k += 1
      }
      if (arr(k) > temp) { //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
        arr(i2) = arr(k)
        i2 = k
        k = k * 2 + 1
      }
      else {
        k = k * 2 + 1
        k = Integer.MAX_VALUE
      }
    }
    arr(i2) = temp //将temp值放到最终的位置

  }

  def swap(arr:Array[Int],i:Int,j:Int):Unit={
    val temp = arr(i)
    arr(i) = arr(j)
    arr(j) = temp
  }



}
